class Solution {
public:
    int maximumRemovals(string s, string p, vector<int>& removable) {
        int n1 = s.size(), n2 = p.size(), n3 = removable.size();
        auto check = [&](int k) -> bool {
            vector<int> state(n1, 1);
            for (int i = 0; i < k; i++) {
                state[removable[i]] = 0;
            }

            int left1 = 0, left2 = 0;
            while (left1 < n1 && left2 < n2) {
                if (state[left1] == 1 && s[left1] == p[left2]) {
                    left1++, left2++;
                } else {
                    left1++;
                }
            }
            cout << k << ' ' << left2 << endl;
            return (left2 == n2);
        };

        int left = 0, right = n3 + 1;
        for (; left < right;) {
            int mid = (left + right) >> 1;
            cout << mid << endl;
            if (check(mid)) {
                // 删少了
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left - 1;
    }
};
class Solution {
public:
    int minimumScore(string s, string t) {
        int n1 = s.size(), n2 = t.size();
        vector<int> suf(n1 + 1);
        suf[n1] = n2; // 极端情况,一个也不匹配
        for (int i = n1 - 1, j = n2 - 1; i >= 0; i--) {
            if (s[i] == t[j]) {
                j--;
            }
            if (j < 0)
                return 0;
            suf[i] = j + 1;
        }
        int ans = suf[0];
        for (int i = 0, j = 0; i < n1; i++) {
            if (s[i] == t[j]) {
                j++;
            }
            ans = min(ans, suf[i + 1] - j);
        }
        return ans;
    }
};
class Solution {
public:
    vector<int> validSequence(string word1, string word2) {
        int n1 = word1.size(), n2 = word2.size();
        vector<int> suf(n1 + 1);
        for(int i = n1 - 1,j = n2 - 1;i >=0;i--){
            if(j >= 0 && word1[i] == word2[j])
            {
                j--;
            }
            suf[i] = j + 1;
        }
        vector<int> ans(n2);
        bool change = false;
        for(int i = 0,j = 0;i < n1;i++){
            if(word1[i] == word2[j] || !change && suf[i + 1] <= j + 1){
                // j 是已经匹配的元素,suf[i + 1] 是需要匹配的元素
                if(word1[i] != word2[j])
                    change = true;
                ans[j++] = i;
                if(j == n2){
                    return ans;
                }
            }
        }
        return {};
    }
};